perm filename LOSS[CLS,LSP]2 blob
sn#833997 filedate 1987-02-05 generic text, type C, neo UTF8
COMMENT ā VALID 00018 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002
C00005 00003
C00009 00004 (defun pr-walk (class)
C00011 00005 Class Precedence List
C00021 00006 /sub
C00034 00007 /sub
C00042 00008 (defun pow (class-name)
C00049 00009 (defun preorder-walk (class)
C00050 00010 common-lisp-object-system/su
C00063 00011 (defun print-nodes ()
C00065 00012 (init)
C00066 00013 common-lisp-object-system/su
C00072 00014 (init)
C00074 00015 Hard Cases
C00077 00016 Common-Lisp-Object-system/su
C00082 00017 (topologically-sort 'a)
C00084 00018 common-lisp-object-system/su
C00092 ENDMK
Cā;
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 () ())
(defclass c6 () ())
(print-nodes)
(topologically-sort 'c1)
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 () ())
(compute-total-order 'c1)
(cpl-less 'c5 'c6)
(cpl-less 'c6 'c5)
*lattice*
*local-info*
(compute-alpha-paths 'c1 *lattice*)
(defun init-local-info (node)
(setf (root *local-info*) node)
(setf (total-order *local-info*) ())
(setf (lattice *local-info*) *lattice*)
(compute-alphabetical-paths *local-info*)
node)
(init-local-info 'c1)
*local-info*
(cpl-less 'c3 'c5)
(in-lattice-order 'c6 'c5)
(in-local-precedence-order 'c6 'c5)
(untrace)
(trace in-kleene-brouwer-order)
(all-nodes *lattice*)
(alphabetical-paths *local-info*)
(*catch 'foo (*throw 'foo 'baz))
(defun cpl-less (node1 node2)
(cond ((eq node1 node2) nil)
(t (let ((p (cpl-less-1 node1 node2)))
(cond ((or (and (in-lattice-order node1 node2)
(in-local-precedence-order node2 node1))
(and (in-lattice-order node2 node1)
(in-local-precedence-order node1 node2))
(eq p (cpl-less-1 node2 node1)))
(error '|Inconsistent Lattice|)
(*throw 'inconsistent-lattice nil))
(t p))))))
(DEFCLASS C1 () ())
(DEFCLASS C2 () ())
(DEFCLASS C3 () ())
(DEFCLASS C4 (C1 C2) ())
(DEFCLASS C5 (C3 C2) ())
(DEFCLASS C6 (C4 C5) ())
(compute-total-order 'c6)
(defun print-nodes ()
(do ((nodes *node-alist* (cdr nodes)))
((null nodes))
(let ((nr (node-record (car nodes))))
(print `(,(name nr) (count = ,(count nr)) (pseudo-order = ,(pseudo-order nr))
(in-degree ,(in-degree nr))
(superclasses
,(do ((l (direct-superclasses nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(successor-supers
,(do ((l (top-supers nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(successor-siblings
,(do ((l (top-siblings nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans))))))))
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(let ((*preorder-counter* 0))
(preorder-walk (find-node-record 'c1)))
(print-nodes)
(topologically-sort 'c1)
= (C1 C2 C3 C4 C6 C5 TOP)
(init)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c2)
= (C2 C3 C5 C4 C6 TOP)
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort)
= (C6 C4 C5 C1 C3 C2 TOP)
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort)
= Inconsistent Lattice
(init)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort 'e7)
= (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)
(init)
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit (food) ())
(defclass spice (food) ())
(defclass food () ())
(defclass pie (apple cinnamon) ())
;(defclass pastry (cinnamon apple) ())
(topologically-sort 'pastry)
(init)
(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())
(topologically-sort 'pie)
(defun pr-walk (class)
(push (name class) *pre*)
(dolist (superclass (direct-superclasses class))
(pr-walk superclass)))
(defun pw-rear (class-name)
(let ((*pre* nil))
(pr-walk (find-node-record class-name))
(let ((ans ()))
(do ((pre *pre* (cdr pre)))
((null pre) ans)
(unless (memq (car pre) ans) (push (car pre) ans))))))
(defun pw-front (class-name)
(let ((*pre* nil))
(pr-walk (find-node-record class-name))
(let ((ans ()))
(do ((pre (reverse *pre*) (cdr pre)))
((null pre) (reverse ans))
(unless (memq (car pre) ans) (push (car pre) ans))))))
(pw-front 'e7)
(init)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
Class Precedence List
I've been searching for a way to explain the class precedence
list computation that is simpler than the existing explanations.
I think it can be explained like this:
We will compute the total order on classes at or above the class, C. Call
the top of the class lattice TOP. Let CL be the set of classes at or
above C. Sort this set according to the relation, <, defined as follows:
Consider C1 and C2 in CL.
1. If there exists a path, P, from C to TOP such that
C1 and C2 are in P, then C1<C2 iff C1 is closer to C
along P. [This is the lattice order.]
2. If C1 and C2 are direct superclasses of C3, where C3 is
in CL, then C1<C2 iff C1 precedes C2 in the local precedence
list for C3. [This is the local precedence order.]
3. Let P1 be the alphabetically least path from C to TOP containing C1.
Let P2 be the alphabetically least path from C to TOP containing C2.
Let C3 and C4 be the first classes in P1 and P2, resp, that differ.
Then C1<C2 if C3<C4.
[This is the Kleene-Brouwer order.]
We will say that there is no total order on a set of classes, CL, above a
class C if there exists two classes C1 and C2 in CL such that C1<C2 and
C2<C1 under this order or if clauses 1. and 2. yield inconsistent results.
That is, there is no total order if the lattice order and local
precedence orders contradict each other immediately or if the overall
relationship is inconsistent. (These two cases are separate because
we want to say that the relation is indifferent as to whether the lattice
order or local precedence order is tested first, but an algorithm
tests one before the other. Note the ``if and only if''s in clauses
1 and 2.)
Before I explain some of the terminology more thoroughly, let me point out
that the order defined by 1 and 3 is called the Kleene-Brouwer ordering on
finite trees. This is good, because it is a well-known ordering, and the
class precedence list is computed using a natural extension to it.
A path from C1 to C2 is defined to be an ordered set of classes CL1...CLn,
such that C1=CL1, C2=CLn, and for every i=1...n-1, CL(i+1) is a direct
superclass of CLi.
We say that a class C is in a path P={C1...Cn} if C=Ci for some i between
1 and n, inclusive.
Let P={C1...Cn} be a path from C1 to Cn. Then we say that C3 is closer to
C1 than C4 in P if there exists a Ci and Cj such that Ci is in P, Cj is in
P,C3=Ci, C4=Cj, and i<j. We extend this terminology in the natural way: we
say that C is the first class in the path P that satisfies some predicate,
PR, to mean that there exists a Ci in P such that PR(Ci) is true and that
if 0<j<i, PR(Cj) is not true.
Let P1={D1...Dn} and P2={E1...Em} be paths from C1 to C2. Note that
D1=E1=C1 and Dn=Em=C2. We say that P1 is alphabetically less than P2 if
P1 and P2 are different and if the following is true:
Let Di and Ei be the first classes in P1 and P2, resp, that
differ. Note that 1<i<n, 1<i<m, and D(i-1)=E(i-1). The
condition is that Di precedes Ei in the local precedence order
for D(i-1).
(This might sound complex, but you can generate the paths in alphabetical
order by doing a depth-first traversal of the tree from C1 to C2, collecting
the paths as you go.)
I think this is simpler because the lattice order and local precedence
have an obvious role in the total order. Also, the Kleene-Brouwer order
depends on looking at the least paths through the classes in question,
which depends on the lattice and local precedence orders, and seeing how
the first different classes in those two paths differ. The effect of the
Kleene-Brouwer condition is to impose an alphabetical order on the
lattice in a natural way.
I think people can understand the relation so defined, and it is easier to
invoke an explicit sorting operation rather than blending the sort with
the computation of the relation, as earlier attempts at it explaining the
computation of the total do.
Of course, I hacked this up (though not very elegantly) and it works well
on the one or two examples I ran it on.
If you want to know what it does on some lattice, send me a note
with a class lattice that is in this syntax and I'll run it:
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 () ())
(defclass c6 () ())
(compute-total-order 'c1) = (C1 C2 C3 C4 C6 C5)
(compute-total-order 'c2) = (C2 C3 C5 C4 C6)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 () ())
(compute-total-order 'c1) = Inconsistent Lattice
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(compute-total-order 'c6) = (C6 C4 C1 C5 C3 C2)
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(compute-total-order 'd6) = Inconsistent Lattice
(defclass c1 () ())
(defclass c2 () ())
(defclass c3 () ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(compute-total-order 'e7) = (E7 E5 C1 E6 E4 C2 E3 C3 E2 E1)
The correct answer is (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3).
(compute-total-order 'e7)
(cpl-less 'c3 'c1)
(compare 'c1 'c3)
(E7 E5 E6 E4 E3 E2 E1 C3 C1 C2)
(cpl-less 'c1 'c2)
(cpl-less 'c2 'c3)
(trace in-kleene-brouwer-order)
(untrace)
(compare 'c3 'e2)
(compare 'e2 'c3)
(trace compare)
(compare 'c1 'c3)
(E7 E5 E6 E4 E3 C3 E2 E1 C1 C2)
(init)
(defclass pie (apple cinnamon) ())
(defclass apple (fruit) ())
(defclass cinnamon (spice) ())
(defclass fruit () ())
(defclass spice () ())
(compute-total-order 'pie)
/sub
common-lisp-object-system
Class Precedence List
This message is long because there are a lot of examples of code running
at the end.
I've been searching for a way to explain the class precedence list
computation that is simpler than the existing explanations. I think we
can explain it fairly well if we relax, a bit, the requirements of
implementations, though we can certainly recommend that implementations go
the extra distance. What I'm proposing is a subset of the behavior that
the Moon algorithm has, but it is simple to explain and understand.
Here it is. We represent a partial order as a set of pairs, (x,y), such
that (x,y) indicates that x<y. Here are the assumed rules of the relation
<.
If x<y and y<z then x<z (transitivity)
If x<y then it is not the case that y<x (asymmetry)
It is not the case that x<x (irreflexivity)
If x<y we'll say that ``x precedes y.'' We then define a partial order on
the components of a class, C1, as follows. Let CL be the components of C1.
If D is a direct superclass of C, where C is in CL, then (C,D) is in the
partial order. If D1 and D2 are direct superclasses of C, where C is in
CL, such that D1 precedes D2 in the local precedence order, then
(D1,D2) is in the partial order. (Note, these correspond to Moon's rules 1
and 2, but we explicitly list the pairs of relations, and we deal with
direct superclasses only.)
Now we topologically sort the elements of CL. This is done as follows.
Select a class C that is not preceded by any other. Put it first in the order.
Remove C from CL and remove all pairs that mention it. This new CL is again
partially ordered by the new pairs. Select a C that is not preceded by
any other and put it next in the order. Continue until CL is empty.
The only way that the algorithm could fail, if there really was a partial
order to start with, would be if there were elements in CL at some point
and every C in CL was preceded by another. If this were true, we could
construct an arbitrary sequence, C1, C2, ... such that Cj+1<Cj. By
transitivity, for all j,k s.t. j<k, Ck<Cj, which implies that Cj is not
equal to Ck. But CL is finite, so some Cj=Ck for some j,k s.t. j<k. This
is a contradiction.
So, if the algorithm fails, we did not have a partial order, which means that
the local precedence order and the lattice order are inconsistent. The algorithm
does signal an error when this happens.
Topological sort runs in C1*M+C2*N time where M is the number of ordered pairs
and N is the number of objects in CL, C1 and C2 some constants.
I hacked this together, and it is 27 lines of code once the data structure
is built. Building the data structure incrementally from a series of
DEFCLASS1's as Moon uses in his examples is another 25 lines of so of code.
The total file is 84 lines long, including the DEFSTRUCT and the code to
make MacLisp think it's Common Lisp enough to run the rest (blush, I
have no Common Lisp to use on SAIL).
The code is an approximate translation of Knuth's algorithm on page 262 of
vol 1 (first edition). It takes the precise DEFCLASS's that define the
sublattice, but it's intended to only illustrate the algorithm at work.
If there are several total orders, the result of the topological sort depends
on the order that the algorithm selects classes that are not preceded by
any others. This depends, generally, on the order that the DEFCLASS's were
evaluated.
I propose that we require implementations to select a total order using an
implementation of topological sort, and that we encourage implementations
to signal an error when several total orders are possible. They can do
this using Moon's algorithm, for example, or by using the topological sort
and having the program notice when there are several classes not preceded
by others from which to select. It could backtrack and determine all of
them, I suppose.
I think this is simpler because many people know topological sort already,
they can understand the partial order in terms of these simple pairs, and
the topological sort algorithm can be explained in a paragraph. People can
also easily see where the non-determinism comes in if there are several
total orders. (Note that most people would know the algorithm after
reading the specification of the partial order as those pairs and seeing
the phrase ``now topologically sort.'')
Here it is running on some examples Moon, Danny, Gregor, and who knows who
else sent out (notice I changed the name of DEFCLASS1 to DEFCLASS). TOP
means the top of the lattice.
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C1 C2 C3 C4 C6 C5 TOP)
;;; Here are the partial order defining pairs for the above example:
;;; (c1,c2)(c1,c6)(c1,c5)(c2,c6)(c6,c5)(c2,c3)(c2,c4)(c3,c4)
;;; (c3,c5)(c4,c6)(c5,top)(c6,top)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort) = (C2 C3 C5 C4 C6 TOP)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort) = Inconsistent Lattice
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort) = (C6 C4 C5 C1 C3 C2 TOP)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort) = (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C2 TOP)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
(topologically-sort) = (E1 D1 D2 C1 C3 C2 TOP)
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass o (top) ())
(defclass b1 (o) ())
(defclass b2 (o) ())
(defclass b3 (o) ())
(defclass b4 (o) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())
(topologically-sort) = (EXAMPLE-1 EX1-1 EX1-2 B1 B2 B3 B4 O TOP)
(defclass o (top) ())
(defclass b1 (o) ())
(defclass b2 (o) ())
(defclass b3 (o) ())
(defclass ex2-1 (b1) ())
(defclass ex2-2 (b2) ())
(defclass ex2-3 (b3) ())
(defclass example-2 (ex2-1 ex2-2 ex2-3) ())
(topologically-sort) = (EXAMPLE-2 EX2-1 EX2-2 B1 EX2-3 B2 B3 O TOP)
(defclass d0 (top) ())
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass e (d0 d1) ())
(defclass f (d1 d2 d3) ())
(defclass g (d1 d2) ())
(defclass h (d0) ())
(defclass foo (e f g h) ())
(topologically-sort) = (FOO E F G H D0 D1 D2 D3 TOP)
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass d4 (d3 d2) ())
(defclass d5 (d2) ())
(defclass d6 (d3 d2 d5 d4) ())
(topologically-sort) = Inconsistent Lattice
(defclass g1 (top) ())
(defclass g2 (top) ())
(defclass g3 (top) ())
(defclass g4 (top) ())
(defclass g5 (g1 g2) ())
(defclass g6 (g2 g3) ())
(defclass g7 (g3 g4) ())
(defclass g8 (g4 g5 g6 g7) ())
(topologically-sort) = Inconsistent Lattice
(defclass this (is much) ())
(defclass is (too) ())
(defclass much (fun!) ())
(defclass too () ())
(defclass fun! () ())
(topologically-sort) = (THIS IS TOO MUCH FUN!)
-rpg-
/sub
common-lisp-object-system
Very Dull Message About Class Precedence Lists
For those who are actively thinking about this issue, here is a followup
on my last message about topological sort. It mostly contains a bunch of
runs of a slightly modified algorithm. The modifications are that it now
reports when multiple orders are possible, and, when there is a choice
between several classes with no predecessors, the algorithm selects the
one that appear first in a preorder treewalk from the class for which the
class precedence list is being computed to the top of the lattice (viewed
as a tree). I believe that this algorithm produces the same results as
the New Flavors algorithm, but it is easier to explain: 1. Compute the
partial order relations; 2. topologically sort; 3. when topological sort
has a choice of several classes to put next, select according to preorder.
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c1)
= (C1 C2 C3 C4 C6 C5 TOP)
(init)
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(topologically-sort 'c2)
= (C2 C3 C5 C4 C6 TOP) Multiple orders possible
(init)
(defclass c1 (c3 c2) ())
(defclass c2 (c3) ())
(defclass c3 (top) ())
(topologically-sort 'c1)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass c4 (c1 c2) ())
(defclass c5 (c3 c2) ())
(defclass c6 (c4 c5) ())
(topologically-sort 'c6)
= (C6 C4 C1 C5 C3 C2 TOP) Multiple orders possible
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass e1 (c1) ())
(defclass e2 (c2) ())
(defclass e3 (c3) ())
(defclass e4 (e3 e2 e1) ())
(defclass e5 (c1 c2) ())
(defclass e6 (c2 c3) ())
(defclass e7 (e5 e6 e4) ())
(topologically-sort 'e7)
= (E7 E5 E6 E4 E3 E2 E1 C1 C2 C3 TOP)
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass d1 (c1) ())
(defclass d2 (c2) ())
(defclass e1 (d1 d2) ())
(topologically-sort 'e1)
= (E1 D1 C1 D2 C2 TOP) Multiple orders possible
(init)
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
(topologically-sort 'e1)
= (E1 D1 D2 C1 C2 C3 TOP) Multiple orders possible
(init)
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d4 (c3 c2) ())
(defclass d5 (c2) ())
(defclass d6 (c3 c2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass b4 (top) ())
(defclass ex1-1 (b1 b3 b4) ())
(defclass ex1-2 (b2 b3) ())
(defclass example-1 (ex1-1 ex1-2) ())
(topologically-sort 'example-1)
= (EXAMPLE-1 EX1-1 B1 EX1-2 B2 B3 B4 TOP) Multiple orders possible
(init)
(defclass b1 (top) ())
(defclass b2 (top) ())
(defclass b3 (top) ())
(defclass ex2-1 (b1) ())
(defclass ex2-2 (b2) ())
(defclass ex2-3 (b3) ())
(defclass example-2 (ex2-1 ex2-2 ex2-3) ())
(topologically-sort 'example-2)
= (EXAMPLE-2 EX2-1 B1 EX2-2 B2 EX2-3 B3 TOP) Multiple orders possible
(init)
(defclass d0 (top) ())
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass e (d0 d1) ())
(defclass f (d1 d2 d3) ())
(defclass g (d1 d2) ())
(defclass h (d0) ())
(defclass foo (e f g h) ())
(topologically-sort 'foo)
= (FOO E F G H D0 D1 D2 D3 TOP)
(init)
(defclass d1 (top) ())
(defclass d2 (top) ())
(defclass d3 (top) ())
(defclass d4 (d3 d2) ())
(defclass d5 (d2) ())
(defclass d6 (d3 d2 d5 d4) ())
(topologically-sort 'd6)
= Inconsistent Lattice
(init)
(defclass g1 (top) ())
(defclass g2 (top) ())
(defclass g3 (top) ())
(defclass g4 (top) ())
(defclass g5 (g1 g2) ())
(defclass g6 (g2 g3) ())
(defclass g7 (g3 g4) ())
(defclass g8 (g4 g5 g6 g7) ())
(topologically-sort 'g8)
= Inconsistent Lattice
(init)
(defclass this (is much) ())
(defclass is (too) ())
(defclass much (fun!) ())
(defclass too (top) ())
(defclass fun! (top) ())
(topologically-sort 'this)
= (THIS IS TOO MUCH FUN!) Multiple orders possible
-rpg-
(defun pow (class-name)
(let ((*preorder-counter* 0))
(preorder-walk (find-node-record class-name))))
(defun preorder-walk (class)
(traverse class))
(defun traverse (class)
(visit class)
(walk class))
(defun visit (class)
(setf (pseudo-order class) (incf *preorder-counter*)))
(defun walk (class)
(visit class)
; (dolist (superclass (direct-superclasses class))
; (visit superclass))
(dolist (superclass (direct-superclasses class))
(walk superclass)))
(defun rem-dup (l)
(cond ((null l) ())
((memq (car l) (cdr l)) (rem-dup (cdr l)))
(t (cons (car l) (rem-dup (cdr l))))))
(defun tr (class-name)
(let ((*pt* ())
(class (find-node-record class-name)))
(visit1 class)
(talk class)
(reverse (rem-dup *pt*))))
(rem-dup (reverse *pt*))))
(defun visit1 (class)
(push (name class) *pt*))
(defun talk (class)
(dolist (superclass (direct-superclasses class))
(visit1 superclass))
(dolist (superclass (direct-superclasses class))
(talk superclass))))
(defun test ()
(init)
(eval (subst () () '(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())))
(eval (subst () () '(DEFCLASS PPTEST-MIXIN (PPTEST3) ()) ))
(eval (subst () () '(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())))
(eval (subst () () '(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())))
(eval (subst () () '(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())))
(eval (subst () () '(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())))
(eval (subst () () '(DEFCLASS PPTEST-BASE () ())))
(topologically-sort 'pptest1)
)
ppltiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
Multiple Total Orders Possible
(PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
(print-nodes)
(PPTEST-BASE (COUNT = 2) (PSEUDO-ORDER = 22) (SUPERCLASSES NIL) (SUCCESSORS
NIL))
(PPTEST-INTERMEDIATE-2 (COUNT = 1) (PSEUDO-ORDER = 20) (SUPERCLASSES (PPTEST-BASE))
(SUCCESSORS (PPTEST-BASE)))
(PPTEST-INTERMEDIATE-1 (COUNT = 1) (PSEUDO-ORDER = 15) (SUPERCLASSES (PPTEST-BASE))
(SUCCESSORS (PPTEST-BASE)))
(PPTEST3 (COUNT = 3) (PSEUDO-ORDER = 18) (SUPERCLASSES (PPTEST-INTERMEDIATE-2))
(SUCCESSORS (PPTEST-INTERMEDIATE-2)))
(PPTEST2 (COUNT = 2) (PSEUDO-ORDER = 13) (SUPERCLASSES (PPTEST-INTERMEDIATE-1))
(SUCCESSORS (PPTEST-INTERMEDIATE-1 PPTEST3)))
(PPTEST-MIXIN (COUNT = 1) (PSEUDO-ORDER = 6) (SUPERCLASSES (PPTEST3)) (SUCCESSORS
(PPTEST3 PPTEST2)))
(PPTEST1 (COUNT = 0) (PSEUDO-ORDER = 2) (SUPERCLASSES (PPTEST-MIXIN PPTEST2
PPTEST3)) (SUCCESSORS (PPTEST3 PPTEST2 PPTEST-MIXIN)))
NIL
(defun order (class-name)
(let ((*cl* ()))
(order1 (find-node-record class-name))
(sortcar
(mapcar #'(lambda (x)(cons (cdr x)(car x))) *cl*)
#'lessp)))
(defun order1 (class)
(unless (assq (name class) *cl*)
(push (cons (name class) (pseudo-order class)) *cl*))
(dolist (super (direct-superclasses class))
(order1 super)))
(ORDER 'pptest1)
((2 . PPTEST1) (6 . PPTEST-MIXIN) (13 . PPTEST2) (15 .
PPTEST-INTERMEDIATE-1) (18 . PPTEST3) (20 . PPTEST-INTERMEDIATE-2) (22 .
PPTEST-BASE))
((1 . PPTEST1) (2 . PPTEST-MIXIN) (3 . PPTEST2) (5 . PPTEST3) (8 . PPTEST-INTERMEDIATE-1)
(10 . PPTEST-INTERMEDIATE-2) (11 . PPTEST-BASE))
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST3 PPTEST-INTERMEDIATE-1
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
(defun preorder-walk (class)
(cond ((< (pseudo-order class) 0))
(t
(dolist (superclass (reverse (direct-superclasses class)))
(preorder-walk superclass))
(setf (pseudo-order class) (decf *preorder-counter*))
)))
Multiple Total Orders Possible
(PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
common-lisp-object-system/su
CPL Computation
As I've mentioned earlier, I wasn't interested in proposing a new
definition of the CPL computation different from what Flavors presents but
in proposing a clear way of describing it.
I took Moon's suggestion and looked for a different ``tiebreaker'' from
preorder treewalk. I have a simple way to describe it, but the naive
implementation has bad running behavior. The fast version is describable,
but the description is horrendous. I think we want to consider what this
all means once the algorithms are presented.
The algorithm is precisely as before, but when the topological sort would
nondeterministically select one class from among a set of equally good
ones, you choose based on a last-visited preorder treewalk.
A last-visited preorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.'' The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order. To walk from C, first C is visited, then we walk from
C1, then we walk from C2, and so on until we finally walk from Cn.
If a class has been visited before, you ignore that visit. That is,
the order is the order in which the last visits to a node are made.
Normally, one computes the preorder treewalk order as a number attached to
the class. Again normally, this number is computed by performing the
preorder treewalk and INCFing a counter. In a preorder treewalk, when a
class already has a preorder number, you do not re-visit that class; the
modification to normal preorder treewalk to obtain last-visited preorder
treewalk is to eliminate this last pruning. The tiebreaker simply looks
at these preorder numbers, choosing the class with the smallest preorder
number.
Notice that a lot of pruning might have been done by the original preorder
walk and that the last-visited preorder walk eliminates all of the
pruning.
Here is some crufty code to compute the normal preorder number into
a slot of the class called the PREORDER:
(defun preorder-walk (class)
(cond ((< 0 (preorder class))) ;already visited
(t (setf (preorder class) (incf *preorder-counter*))
(dolist (superclass (direct-superclasses class))
(preorder-walk superclass)))))
Here is the modified code:
(defun lv-preorder-walk (class)
(setf (preorder class) (incf *preorder-counter*))
(dolist (superclass (direct-superclasses class))
(lv-preorder-walk superclass)))
This is, of course, less efficient than the previous code, though it looks
simpler. One can get a fast algorithm by doing what could be called a
reversed reversed postorder treewalk (``moonwalk,'' for short).
We define reversed postorder treewalk and then modify that to be reversed
reversed postorder treewalk.
A reversed postorder treewalk is defined in terms of the order in which
classes are visited while performing a process called ``walking from a
class.'' The following is a recursive definition of walking from a class.
Let C be a class and let {C1...Cn} be its direct superclasses in the local
precedence order. Classes are visited unless they have already been
visited. To walk from C, first we walk from Cn, then we walk from Cn-1,
and so on until we finally walk from C1. Finally we visit C. A reversed
reversed postorder treewalk visits classes in precisely the reverse order
that they are visited in a reversed postorder treewalk.
Implementationally, moonwalk isn't too bad. You place reversed postorder
numbers on each class at or above the class of interest, and ties are
broken by selecting the class with the largest reversed postorder number
(note that we chose the smallest number in the preorder tiebreaker).
Selecting the largest effects the second reversing.
Here is the code to do this:
(defun walk (class)
(cond ((< 0 (rpostorder class)))
(t (dolist (superclass (reverse (direct-superclasses class)))
(walk superclass))
(setf (rpostorder class) (incf *counter*)))))
This algorithm works on all of the examples I sent before plus the
two killers Moon sent Sunday.
The question now becomes: Is this what we really want? I claim that
it doesn't matter too much what the tiebreaker is, because it is always
possible to reformulate the lattice and use direct superclasses to
achieve the desired effect. The fact the there are millions of flavors
that use the moonwalk tiebreaker doesn't support the claim that
the moonwalk tiebreaker is right: Perhaps the flavors have been carefully
crafted to inherit properly.
The explicit local precedence orders are the means by which programmers
specify the ordering they want. The tiebreaker simply makes the total
order well-defined. The tiebreaker is not intended to be a ``model''
of the class precedence list. If the topological sort produces a unique
order, that order is intuitive; the cases where tiebreaking happens is
ad hoc and is no intuitive.
In the spirit of trying to figure out the New Flavors algorithm in order
to be able to present it well, my algorithms wizard and I have tried come
up with a more easily explainable algorithm that mimics the New Flavors
and does not have topological sort as an explicit part of it. We failed,
though we have not yet written down an example for which it fails.
[I only mention this because I promised to show this algorithm in my last
message.]
Finally, I'm not sure that the first of Moon's killers has a very intuitive
Flavors order. Here it is again:
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
The Flavors order is (ptest1 ptest2 ptest3 ptest4 ptest5).
Why is ptest4 before ptest5? Here's what the thing looks like:
top------
| |
pt4 |
| |
|-----------pt5
| | /
pt2 pt3 /
\ | /
\ | /
pt1
pt5 is a direct superclass of pt1 and pt4 isn't. One could argue that pt5
is the last of the direct superclasses, so it should come after the
earlier direct superclasses and all of their superclasses; in this case
you get to pt4 first because it is above pt3, which precedes pt5. But,
does being mentioned first in a defclass count for anything? If so, you
get to pt5 by passing through the first of the direct superclasses of pt1
(pt1 to pt2 to pt5) whereas you get to pt4 by passing through the second
of the direct supeclasses of pt1 (pt1 to pt3 to pt4), and there are
exactly the same number of intermediate classes. Everything says pt5
should precede pt4, but Flavors doesn't. I believe this to be a serious
problem.
Finally, my algorithms wizard and I studied the New Flavors CPL
computation description and think there is a performance problem with the
algorithm it describes. Consider the following graph of 4n+1 classes:
(defclass Ai (Bi Ci) ())
(defclass Bi (Di Ai+1) ())
(defclass Ci (Di) ())
(defclass Di () ())
for 0 <= i < n.
Here are the classes for n=2.
(defclass a0 (b0 c0) ())
(defclass b0 (d0 a1) ())
(defclass c0 (d0) ())
(defclass d0 () ())
(defclass a1 (b1 c1) ())
(defclass b1 (d1 a2) ())
(defclass c1 (d1) ())
(defclass d1 () ())
The New Flavors algorithm, as described, seems to take n+1 passes, though
there is exactly one total order possible.
Given that reversed reversed postorder treewalk (or last-visited preorder)
is the tiebreaker, that there is at least one suspicious Flavors-order
example, that people can formulate their lattices as they want to get the
right inheritance, that there is no intuition to any order beyond what the
topological sort gives you, and there is a possible performance problem
with the algorithm described in the New Flavors document, I have now
flipped my bit on this issue from wanting to mimic the Flavors order
to insisting on preorder tiebreaker with topological sort.
-rpg-
(defun print-nodes ()
(do ((nodes *node-alist* (cdr nodes)))
((null nodes))
(let ((nr (node-record (car nodes))))
(print `(,(name nr) (count = ,(count nr))
(superclasses
,(do ((l (direct-superclasses nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans)))
(siblings
,(do ((l (direct-siblings nr) (cdr l))
(ans ()))
((null l) (reverse ans))
(push (name (car l)) ans))))))))
(init)
(defclass c1 (c2 c6 c5) ())
(defclass c2 (c3 c4) ())
(defclass c3 (c5) ())
(defclass c4 (c6) ())
(defclass c5 (top) ())
(defclass c6 (top) ())
(walk 'c1)
((WALKING E7) (COUNT 0))
((WALKING E5) (COUNT 0))
((WALKING C1) (COUNT 1))
((WALKING C2) (COUNT 3))
((WALKING E6) (COUNT 0))
((WALKING C2) (COUNT 2))
((WALKING C3) (COUNT 2))
((WALKING E4) (COUNT 0))
((WALKING E3) (COUNT 0))
((WALKING C3) (COUNT 1))
((WALKING E2) (COUNT 0))
((WALKING C2) (COUNT 1))
((WALKING E1) (COUNT 0))
((WALKING C1) (COUNT 0))
((WALKING TOP) (COUNT 2))
(E7 E5 E6 E4 E3 E2 E1 C1)
(init)
(defclass a0 (b0 c0) ())
(defclass b0 (d0 a1) ())
(defclass c0 (d0) ())
(defclass d0 () ())
(defclass a1 () ())
(defclass y (a0) ())
(defclass w (x y z) ())
(topologically-sort 'w)
(init)
(defclass a0 (b0 c0) ())
(defclass b0 (d0 p) ())
(defclass c0 (d0 q) ())
(defclass d0 () ())
(defclass y (a0) ())
(defclass w (x y z) ())
(defclass p (p1 p2 p3) ())
(defclass q (q1 q2 q3) ())
(topologically-sort 'w)
common-lisp-object-system/su
Elaboration on the Non-intuitiveness of New Flavors Algorithm...
...and other related issues.
Remember the funny little configuration of classes mentioned
in an earlier message
(defclass Ai (Bi Ci) ())
(defclass Bi (Di Ai+1) ())
(defclass Ci (Di) ())
(defclass Di () ())
for 0 <= i < n.
Here's what it looks like:
A1
D0 /
| \ /
| \/
| /\
| / \
B0 C0
\ /
\ /
\/
A0
Suppose we are following the New Flavors description of how to compute the
CPL for A0. We start walking through this in depth-first manner starting
at A0. We visit/output A0, visit/output B0, visit D0, visit A1,
visit/output C0, and then visit/output D0. There is no path in depth-first
order with which to get to A1 again, so the first depth-first pass is
over. We notice A1 has not been output and walk it again, outputting A1
last. If A1 is the root of another copy of this, we cannot visit up
through it on the first pass.
If there are classes to the right of A0, they wil be visited and probably
output during the first pass. When the second pass is made, A1 will
be output.
Let's call this configuration the ``MeLast.''
Now consider the following configuration:
T1 T2 T3
| | |
D E F
\ | /
\ | /
\ | /
\|/
C
where C is a class and T1, T2, T3 are independent lattices, except for a
common top. What does intuition say? It says that all of T1 should be
together, all of T2 should be together, and all of T3 should be together,
each group in in some order relative to one another, and the order within
each group unknown. One could argue T1 should precede T2 should precede
T3, but I won't. Suppose that T1 has a MeLast in it, and neither T2 nor T3
does. Then some part of T1 - namely A0, B0, C0, and D0 - will come
early on, then parts of T2 and T3, and finally A1 will be last.
Similar situations hold for T2 and T3, but in all cases, A1 will be last,
assuming there are no other MeLast-like configurations in the T groups.
The intuition is gone.
Here is an example:
MeLast
|
X Y Z
\ | /
\|/
W
The New Flavors order is:
W,X,Y,A0,B0,C0,D0,Z,A1
The gabriel order is:
W,X,Y,A0,B0,C0,D0,A1,Z
Notice that in the gabriel order, the Y/MeLast guys are together
between Y and Z.
The existence of a MeLast configuration is purely an artifact of the
multiple passes that the New Flavors CPL computation does. If it had
a way to remember to redo A1 as soon as its predecessor, D0, was cleared
up, it would not need to make another pass through the lattice.
The MeLast configuration also proves that no algorithm based on
topological sort with a tiebreaker that is like a single-pass,
single-stack treewalk is equivalent to the New Flavors computation. I
haven't thought through the exact constraints, but preorder, reversed
reversed postorder, and things like that as the tiebreaker in conjunction
with topological sort cannot be the same as New Flavors, because they will
put classes in the groups T1, T2, and T3 together.
This increases the strength of my belief that the New Flavors algorithm is
not suitable for the CLOS standard.
-rpg-
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
(print-nodes)
(let ((*walk-counter* 0)) (walk (find-node-record 'ptest1)))
;;; Hard Cases
(init)
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(topologically-sort 'a)
= (A B C D E F X Y)
(init)
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1)
= (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
(init)
(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())
(DEFCLASS PPTEST-MIXIN (PPTEST3) ())
(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())
(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())
(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())
(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())
(DEFCLASS PPTEST-BASE () ())
(topologically-sort 'pptest1)
= (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
moon@stony-brook.scrc.symbolics.com/su
Tiebreaker
You're right, it looks encouraging. To make sure I have it right,
could you tell me what you get on this lattice for E1?
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
My reading of your algorithm says that we start:
e1 d1 d2 c1
At this point either c2 or c3 could come next. Scanning right to
left, d2 comes first, and so c3 is next, then c2. The final order
is:
e1 d1 d2 c1 c3 c2 top
I might be misreading your algorithm, so I'm simply asking for
confirmation. It's hard to know what is most intuitive in this case.
Also, if you could send some more examples, I'm trying to get a superfast
algorithm to do the CPL computation.
-rpg-
Common-Lisp-Object-system/su
CPL Tiebreaker
Ugh, bletch. I think I am really going to regret having written
this message. I think I found the tiebreaker. It passes all of
the hard intuitive cases, which I'll list below, along with all
of the cases ever mailed out.
The tiebreaker applies when there is more than one class with
no predecessors. The tiebreaker has two cases. The first case
is based on this reasoning by Danny (I'll paraphrase):
``If the user has a class and splits that class into two classes with no
other references to the direct superclass, there should be no chance of
any interaction with any other class used as a mixin. Hence one wants all
superclasses of a class to follow as soon as possible after the class they
are related to.''
This is very intuitive, and preorder treewalk is very intuitive. So
we do Danny's condition first and then preorder treewalk. Danny's
condition means this:
We define a relation called unique direct subclass. C is the unique direct
subclass of D if C is the only direct subclass of D. If class X was just
output and X is a unique direct subclass of some class D, D immediately
follows X. Otherwise, ties are broken by preorder treewalk (not
last-visited).
This means that we treat parts of the lattice that look like this:
\|/
D
|
C
/|\
as if they looked like this:
\|/
(D,C)
/|\
[Actually, the above picture is exactly how I looked when I discovered
this tiebreaker.]
Here are the hard cases:
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(topologically-sort 'a) = (A B C D E F X Y)
Well, this is simply preorder treewalk at work.
(DEFCLASS PTEST1 (PTEST2 PTEST3 PTEST5) ())
(DEFCLASS PTEST2 (PTEST5) ())
(DEFCLASS PTEST3 (PTEST4) ())
(DEFCLASS PTEST4 () ())
(DEFCLASS PTEST5 () ())
(topologically-sort 'ptest1) = (PTEST1 PTEST2 PTEST3 PTEST4 PTEST5)
In this one, PTEST3 is the unique direct subclass of PTEST4, so when
PTEST3 is output, PTEST4 and PTEST5 could come next. Preorder would
say PTEST5 is next, but Danny's rule overrides that.
(DEFCLASS PPTEST1 (PPTEST-MIXIN PPTEST2 PPTEST3) ())
(DEFCLASS PPTEST-MIXIN (PPTEST3) ())
(DEFCLASS PPTEST2 (PPTEST-INTERMEDIATE-1) ())
(DEFCLASS PPTEST3 (PPTEST-INTERMEDIATE-2) ())
(DEFCLASS PPTEST-INTERMEDIATE-1 (PPTEST-BASE) ())
(DEFCLASS PPTEST-INTERMEDIATE-2 (PPTEST-BASE) ())
(DEFCLASS PPTEST-BASE () ())
(topologically-sort 'pptest1)
= (PPTEST1 PPTEST-MIXIN PPTEST2 PPTEST-INTERMEDIATE-1 PPTEST3
PPTEST-INTERMEDIATE-2 PPTEST-BASE)
This one is nearly the same as the one before.
This addition condition adds no complexity to the algorithm, because
we compute the in-degrees of each class at DEFCLASS time.
-rpg-
(topologically-sort 'a)
(init)
(DEFCLASS A (B C D E F) ())
(DEFCLASS B (F X) ())
(DEFCLASS C (F Y) ())
(DEFCLASS D (F X) ())
(DEFCLASS E () ())
(DEFCLASS F () ())
(DEFCLASS X () ())
(DEFCLASS Y () ())
(defun test ()
(init)
(eval (subst () () '(defclass c1 (top) ())))
(eval (subst () () '(defclass c2 (top) ())))
(eval (subst () () '(defclass c3 (top) ())))
(eval (subst () () '(defclass d1 (c1 c2) ())))
(eval (subst () () '(defclass d2 (c1 c3) ())))
(eval (subst () () '(defclass e1 (d1 d2) ())))
(topologically-sort 'e1))
(init)
(defclass green-turtles (turtles green-things) ())
(defclass turtles (animate-things) ())
(defclass green-things (animate-things) ())
(topologically-sort 'green-turtles)
(init)
(defclass q (c d) ())
(defclass c (a b) ())
(defclass d (a b) ())
(defclass a (x)())
(defclass b (x) ())
(topologically-sort 'q)
common-lisp-object-system/su
CPL etc
After a day of meetings I was finally able to get back to our favorite
topic. Moon's tiebreaker variant admits a linear implementation, which is
pretty good. I have some questions about whether we think it is intuitive:
(defclass c1 (top) ())
(defclass c2 (top) ())
(defclass c3 (top) ())
(defclass d1 (c1 c2) ())
(defclass d2 (c1 c3) ())
(defclass e1 (d1 d2) ())
At some point Danny mentioned that the ``right'' order for this is
(E1 D1 D2 C1 C2 C3 TOP)
The new algorithm (and New Flavors, I think) produces
(E1 D1 D2 C1 C3 C2 TOP)
Is this less intuitive? More later.
Some people might have been confused by Moon's description. It read:
``When topological sort finds multiple candidates to go in next, choose the
candidate that has a direct subclass rightmost in the class precedence list
computed so far. ***If that subclass has more than one direct superclass
among the candidates, take the superclass that is most specific according
to the subclass's local precedence order.***''
The condition described in the sentence between the asterisks cannot
happen, so you shouldn't try to understand it. A candidate for
entering the final CPL has no predecessors, which means that all of its
siblings to the left have already been placed in the CPL, and so none of
them can be candidates to go next.
I think that in worrying about the CPL we have to keep in mind that most
people will operate under the following model: The direct superclasses
mentioned in the DEFCLASS form and their relative order are important. The
system will then provide some arbitrary total order, and the program will
have to be massaged until it works - simply because no one can understand
the algorithm. This is the model that KDO will have; KDO is no wimp.
Many people will wish they can simply supply their own ordering algorithm.
Here is a simple example, which many of you have seen before. There are 4
classes, perhaps poorly chosen:
Animate-things
blush-method = turn-pink
noseup-method = become-haughty
|
|
/ \
/ \
/ \
Turtles Green-animals
noseup-method = pick-up-pen blush-method = turn-purple
\ /
\ /
\ /
|
|
Green-turtles
Animate-things has two methods, blush-method and noseup-method. The effect of
the blush-method is to change colors and the effect of the noseup-method is
to change the attitude of the object to haughtiness. The first subclass is
Turtles, like LOGO turtles. The noseup-method shadows the animate-things method,
and the effect of it is to pick up the pen; the blush-method is ok. The second
subclass is Green-animals, and the blush-method is different, because when
a green thing turns pink, it really turns purple.
The final class is Green-turtles. This might be a dumb thing to do, but
the user's intuition might be reasonable. He sees that the Turtle noseup-method
is good, and that the Green-animals blush method is good, so he inherits from
both. But he has to mention Turtles and Green-animals in some order. If he
mentions them in the above order, he gets the wrong blush-method; if he reverses
them he gets the wrong noseup-method.
The solution is to reformulate the classes into more parts with hairy
relationships. A similar problem can happen when a user wants to inherit
slots. One can imagine an asymptotic situation where each DEFCLASS has
exactly one slot and you build your classes by the shopping cart method.
The user of the above class lattice believes that the CPL will reflect a
breadth-first CPL. The depth-first nature of all CPL computations so far
reflects a desire for ``transparency'' of subclass-superclass inheritance.
Perhaps we need to have a notation for inheriting from a set of
superclasses in no partocular order, which would signal the CPL
computation to go breadth-first. Maybe another partial solution is some
means of having generic functions be able to distinguish instances of
``this very class'' rather than instances of this very class or of its
subclasses.
In any event, what we are doing by defining the CPL computation as we
are is to provide a mechanism for people to curse the standard. Perhaps
it is necessary to have such a well-defined default, but maybe we should think
about a variety of alternatives from which the user can select as well
as an alternative to roll your own.
-rpg-